package com.search;

import java.util.HashMap;
import java.util.Map;

public class MinPOverigeStr {
	public static void main(String[] args) {
		String a  ="ADOBECODEBANC";
		String b  ="ABC";
		String res = new MinPOverigeStr().minWindow(a, b);
		System.out.println(res);
	}
	public String minWindow(String s, String t) {
        int left = 0,right = 0;
		Map<Character,Integer> map = new HashMap();
		Map<Character,Integer> Windows = new HashMap();
		for(char ch : t.toCharArray())
			map.put(ch, map.getOrDefault(ch, 0)+1);
		int start = 0,end = 0,vaild = 0;
		int minString = Integer.MAX_VALUE;
		while(right < s.length()) {
			char ch = s.charAt(right);
			right++;
			
			if(map.containsKey(ch)) {
				
				Windows.put(ch, Windows.getOrDefault(ch, 0)+1);
				if(Windows.get(ch).equals(map.get(ch)))
					vaild++;
			}
			while(vaild == map.size()) {
				if(right - left < minString) {
					minString = right - left;
					start = left;
					end = right;
				}
				char ch2 = s.charAt(left);
				left++;
				if(map.containsKey(ch2)) {
					if(Windows.get(ch2).equals(map.get(ch2))) 
						vaild--;
					Windows.put(ch2, Windows.getOrDefault(ch2, 0)-1);
			}
			}
        }
		 return minString == Integer.MAX_VALUE ? "" : s.substring(start, end);
	}
}
